﻿/** PRIORITYQUEUE CLASS
 * Author: Preeti Francis
 * User ID : pxfranci@scotty.cs.wichita.edu
 * WSU ID: S578F746
 * Course: CS771 
 * Sem: S2014
 * 
 * Description of Class : The PriorityQueue<Cost, List<Node>> class functions as a priority queue data structure. 
 * It uses generics to take the priority into account by declaring a type "Cost" and uses a generic list of type "Node".
 * It keeps the list in sorted order using the SortedDictionary implementation of dotnet.  
 * **/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _8PiecePuzzle.DataStructures
{
    public class PriorityQueue<Cost, Node>
    {
        //The innerList is the main data structure of the priority queue using generic types : Cost and Node
        private SortedDictionary<Cost, List<Node>> innerList = new SortedDictionary<Cost, List<Node>>();

        //Gets a readonly enumerable of the priority queue
        public SortedDictionary<Cost, List<Node>> GetEnumerator()
        {
           return innerList;
        }

        //Pushes (enqueues) the new element based on it's priority into the queue
        public void Enqueue(Cost priority, Node value)
        {
            List<Node> nodeList;

            if (!innerList.TryGetValue(priority, out nodeList))
            {
                nodeList = new List<Node>();
                
                innerList.Add(priority, nodeList);
            }
            
            nodeList.Insert(0,value);
        }

        //Pops (dequeues) the first element at the smallest priority 
        public Node Dequeue()
        {
            var keyValuePair = innerList.First();

            var firstElement = keyValuePair.Value.ElementAt(0);
            
            keyValuePair.Value.RemoveAt(0);// Dequeue();
    
            //If there are no entries for the recently dequeued cost
            if (keyValuePair.Value.Count == 0) 
                innerList.Remove(keyValuePair.Key);
            
            return firstElement;
        }

        //Finds and replaces the old higher priority node with the new lower priority node
        public void UpdatePriorityForNode(Cost newPriority, Cost oldPriority, Node oldNode , Node updatedNode)
        {
            //Finds the node list at the old priority value
            var nodesAtOldPriorityValue = innerList.First(n => n.Key.Equals(oldPriority));

            //Removes the old node from this list
            nodesAtOldPriorityValue.Value.Remove(oldNode);
            
            //If the list is empty for that cost value then remove the key
            if (nodesAtOldPriorityValue.Value.Count == 0) 
                innerList.Remove(nodesAtOldPriorityValue.Key);

            //Add new node against new priority
            Enqueue(newPriority, updatedNode);            
        }

        //Checks if frontier is empty
        public bool IsEmpty
        {
            get { return !innerList.Any(); }
        }
    }
}
